A well known technique for digital data transformation is to employ the digital data to be transformed as an address to a look up table (LUT) or electronic memory storing a transformation of the digital data to be transformed. Each combination of bits specifies a single location in memory which stores the transformation of the data element corresponding to that combination of bits. LUTs are used in many types of applications such as in color image processing in color pre-press situations.
Memory volume requirements for LUTs are determined by the number of combinations of bits of the input data, as well as by the depth of representation. In color transformation applications, in which a color space may include 224 colors, or more than 16 million colors, a memory having more than 16 million entries or cells may be required, as shown in prior art FIG. 1. This volume of memory is expensive. Also, loading and modification processes become extremely time consuming.
Techniques for reducing memory size are known. These techniques result in a reduction of transformation accuracy to a greater or lesser extent. One such technique, as illustrated in prior art FIG. 2, is to provide only a small number of memory cells corresponding to only a small fraction of the possible input values, such as only 4096 memory cells instead of providing more than 16 million memory cells. Output values for all remaining possible input values, to which no memory cell is assigned, are computed by interpolation or extrapolation based on the distances of an individual input value from the cell addresses which are closest to the individual input value.
A LUT in which the number of possible input values which have a memory cell assigned to them is only a small fraction of the total number of possible input values is also termed herein a "low resolution" LUT.
According to this technique, the majority of transformations are not derived directly from the LUT, since the majority of input values to be transformed do not address any of the memory cells of the LUT. Instead, transformed data for these input values is computed by interpolation from the contents of adjacent memory cells. The factor of gain in memory volume and in loading time is equal to the factor of loss of transformation resolution.
One disadvantage of this method is that LUTs are often employed to represent non-linear transformations in which output values whose addresses fall intermediate a plurality of LUT cells are not linear combinations of the contents of those LUT cells. For these transformations, the results of linear interpolation procedures are normally inaccurate. Furthermore, the inaccuracies introduced by the interpolation process are normally not uniform across the data space to be transformed, but vary thereacross.
For example, for some color spaces, the nonuniformity of the inaccuracies introduced by standard color transformation interpolation processes is such that dark colors are distorted because they are transformed with substantial inaccuracy. Colors which are distorted substantially when they are transformed by interpolation are believed to be colors for which the perception of the human eye is non-linear relative to the actual physical properties of the colors perceived.
U.S. Pat. Nos. 4,941,029 and 4,992,861, both to D'Errico, disclose a technique for reducing memory size which is described as causing relatively little reduction of transformation accuracy. D'Errico provides a method for employing a LUT for interpolation purposes in which an interpolation algorithm with special features is employed.
Published European Application 0366309 to IBM describes a color image quantization system in which color data representative of an input color space of a picture is loaded into a single LUT. The representative data is determined by repeated division of the input color space of the picture into K child-spaces, where K is the number of cells in the LUT. The order of division is dependent upon the distribution of original image pels within the existing child-spaces. Eventually, the distribution of pels within the child-spaces is nearly uniform, thereby maintaining image quality for images having a given distribution of pels within the input color space.
The criterion according to which the IBM method operates is an image-specific criterion whereby precedence is given to color subspaces which are densely populated with image pels. The method is not operative to give precedence to color subspaces in which the non-linearity of the color transformation is particularly pronounced.
Also, the LUT disclosed in the above-referenced IBM document is addressed by nominal index values assigned to each pel rather than by the actual color of each pel. Consequently, it is impossible to carry out a meaningful interpolation process.
The eventual set of child-spaces defined by the IBM method typically includes child-spaces of different sizes. For example, FIG. 5 of the above-referenced IBM document is a conceptual diagram of a divided color-space management list. As shown, the eventual set of child-spaces in FIG. 5 includes 7 child-spaces on level 1, 7 child-spaces on level 2 and 7 child-spaces on level 3. The size of the child-spaces on levels 1, 2 and 3 are 1/8, 1/(8.times.8) and 1/(8.times.8.times.8), respectively.
SUMMARY OF THE INVENTION
The present invention seeks to provide a color transformation apparatus and technique which require relatively little memory but which result in relatively high transformation accuracy.
The apparatus and methods of the present invention are useful in any color transformation application, such as color reading, color writing, digital color modification, and combinations of these, where color reading is defined as transforming an analog representation of a color image into a digital representation thereof, color writing is defined as transforming a digital representation of a color image into an analog representation thereof and digital color modification is defined as modifying a first digital representation of a color image, thereby to obtain a second digital representation of a color image, with or without use of a real-time display screen.
In the present discussion, the term "color image" is not intended to exclude images which are gradations of a single tone such as black and white images, and the following definitions are employed:
Analog representation of a color image: A representation of a color image which resembles or is analogous to the color image itself or which is perceivable by the human eye as a color image. The representation may appear upon any substrate such as a transparency, photograph, CRT display, or printed page.
Digital representation of a color image: A representation of a color image which is expressed in discrete symbols such as numerical symbols. For example, a digital file including a plurality of numerical values corresponding to a plurality of pixels into which the color image has been divided, each such numerical value representing some aspect pertaining to the colored appearance of the corresponding pixel.
According to the technique of the present invention, an input data space is partitioned into a plurality of input data subspaces which are normally not of equal size. The input data in each of the plurality of subspaces addresses a corresponding one of a plurality of LUTs which may be of equal size but typically are not of equal resolution. In other words, the ratio of the size of each LUT to the size of the input data subspace which it is operative to transform varies over the plurality of LUTs.
A particular advantage of this method is that input values, such as bright colors, which are relatively insensitive to interpolation error may be grouped in large subspaces whereas input values, such as dark colors, which are relatively sensitive to interpolation error may be grouped in small subspaces. This grouping provides high resolution transformation apparatus for sensitive input data subspaces and highly compact transformation apparatus for non-sensitive input data subspaces. The subspaces need not be vector spaces in the mathematical sense.
There is thus provided in accordance with a preferred embodiment of the present invention color transformation apparatus for transforming an input color space into an output color space and including a first LUT for transforming a first portion of the input color space into a corresponding first portion of the output color space, a second LUT for transforming a second portion of the input color space into a corresponding second portion of the output color space, and a control unit for channeling input values included in the first and second portions of the color space to the first and second LUTs respectively.
Further in accordance with a preferred embodiment of the present invention, the ratio between the number of memory cells in the first LUT and the number of possible input values channeled thereto differs from the corresponding ratio for the second LUT.
Still further in accordance with a preferred embodiment of the present invention, the input color space also includes at least one more portion thereof and the color transformation apparatus also includes at least one more LUT for transforming a corresponding one of the at least one more portions of the input color space into a corresponding portion of the output color space, the control unit also being operative to channel input values included in each of the at least one more portions of the input color space to a corresponding one of the at least one more LUTs.
There is also provided in accordance with a preferred embodiment of the present invention a color transformation method for operating a color transformation on an input color space, thereby to transform the input color space into an output color space, including the steps of defining first and second portions of the input color space, channeling input values included in the first and second portions of the input color space, respectively, to first and second LUTs respectively, employing the first LUT to transform the first portion of the input color space into a corresponding first portion of the output color space, and employing the second LUT to transform the second portion of the input color space into a corresponding second portion of the output color space.
Further in accordance with a preferred embodiment of the present invention, the step of employing a first LUT includes the step of employing a first interpolation algorithm to interpolate from the first LUT, thereby to compute an output value corresponding to an input value within the first portion of the color space which does not appear in the first LUT.
Still further in accordance with a preferred embodiment of the present invention, the step of employing a second LUT includes the step of employing a second interpolation algorithm to interpolate from the second LUT, thereby to compute an output value corresponding to an input value within the second portion of the color space which does not appear in the second LUT, and the first interpolation algorithm is not the same as the second interpolation algorithm.
Additionally in accordance with a preferred embodiment of the present invention, the first and second portions of the input color space are defined independently of any particular set of input values within the input color space.
There is also provided in accordance with yet a further preferred embodiment of the present invention color transformation apparatus for transforming an input color space into an output color space and including a first LUT for transforming a first portion of the input color space into a corresponding first portion of the output color space, and at least one additional LUT for transforming corresponding at least one additional portions of the input color space into corresponding at least one portions of the output color space, each of the first and at least one additional LUTs including a plurality of memory cells, thereby defining at least two pluralities of memory cells, such that, for each LUT, each individual memory cell represents a subportion of the input color space, thereby to define a plurality of subportions corresponding to each LUT, wherein, for each LUT, the plurality of subportions are of uniform size.
Further in accordance with a preferred embodiment of the present invention, the color transformation apparatus also includes a control unit for receiving input values of the input color space and for channeling input values included in an individual one of the first and at least one additional portions of the input space, respectively, to a corresponding one of the first and at least one additional LUTs, respectively.
Still further in accordance with a preferred embodiment of the present invention, the at least two pluralities of memory cells are not equal in number.
Additionally in accordance with a preferred embodiment of the present invention, the first portion of the input color space includes the entire input color space.
Still further in accordance with a preferred embodiment of the present invention, the first and second portions of the input color space are defined irrespective of the distribution of any particular set of input values within the input color space.
Additionally in accordance with a preferred embodiment of the present invention, at least one of the first and second portions of the input color space includes color values in close proximity over which the transformation varies substantially, and/or memorial colors.
Still further in accordance with a preferred embodiment of the present invention, the input color space portions corresponding to all but one of the LUTs include color values in close proximity over which the transformation varies substantially, and/or memorial colors.